/*  Copyright (C) 2014-2021 FastoGT. All right reserved.

    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions are
    met:

        * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
        * Redistributions in binary form must reproduce the above
    copyright notice, this list of conditions and the following disclaimer
    in the documentation and/or other materials provided with the
    distribution.
        * Neither the name of FastoGT. nor the names of its
    contributors may be used to endorse or promote products derived from
    this software without specific prior written permission.

    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#pragma once

#include <iterator>
#include <memory>
#include <type_traits>

#include <common/macros.h>

namespace common {

template <typename T>
class CheckedContiguousIterator {
 public:
  using difference_type = std::ptrdiff_t;
  using value_type = std::remove_cv_t<T>;
  using pointer = T*;
  using reference = T&;
  using iterator_category = std::random_access_iterator_tag;

  // Required for converting constructor below.
  template <typename U>
  friend class CheckedContiguousIterator;

  constexpr CheckedContiguousIterator() = default;

#if defined(_LIBCPP_VERSION)
  // The following using declaration, single argument implicit constructor and
  // friended `__unwrap_iter` overload are required to use an optimized code
  // path when using a CheckedContiguousIterator with libc++ algorithms such as
  // std::copy(first, last, result), std::copy_backward(first, last, result),
  // std::move(first, last, result) and std::move_backward(first, last, result).
  //
  // Each of these algorithms dispatches to a std::memmove if this is safe to do
  // so, i.e. when all of `first`, `last` and `result` are iterators over
  // contiguous storage of the same type modulo const qualifiers.
  //
  // libc++ implements this for its contiguous iterators by invoking the
  // unqualified __unwrap_iter, which returns the underlying pointer for
  // iterators over std::vector and std::string, and returns the original
  // iterator otherwise.
  //
  // Thus in order to opt into this optimization for CCI, we need to provide our
  // own __unwrap_iter, returning the underlying raw pointer if it is safe to do
  // so.
  //
  // Furthermore, considering that std::copy is implemented as follows, the
  // return type of __unwrap_iter(CCI) needs to be convertible to CCI, which is
  // why an appropriate implicit single argument constructor is provided for the
  // optimized case:
  //
  //     template <class InIter, class OutIter>
  //     OutIter copy(InIter first, InIter last, OutIter result) {
  //       return __copy(__unwrap_iter(first), __unwrap_iter(last),
  //                     __unwrap_iter(result));
  //     }
  //
  //     Unoptimized __copy() signature:
  //     template <class InIter, class OutIter>
  //     OutIter __copy(InIter first, InIter last, OutIter result);
  //
  //     Optimized __copy() signature:
  //     template <class T, class U>
  //     U* __copy(T* first, T* last, U* result);
  //
  // Finally, this single argument constructor sets all internal fields to the
  // passed in pointer. This allows the resulting CCI to be used in other
  // optimized calls to std::copy (or std::move, std::copy_backward,
  // std::move_backward). However, it should not be used otherwise, since
  // invoking any of its public API will result in a CHECK failure. This also
  // means that callers should never use the single argument constructor
  // directly.
  template <typename U>
  using PtrIfSafeToMemmove = std::enable_if_t<std::is_trivially_copy_assignable<std::remove_const_t<U>>::value, U*>;

  template <int&... ExplicitArgumentBarrier, typename U = T>
  constexpr CheckedContiguousIterator(PtrIfSafeToMemmove<U> ptr) : start_(ptr), current_(ptr), end_(ptr) {}

  template <int&... ExplicitArgumentBarrier, typename U = T>
  friend constexpr PtrIfSafeToMemmove<U> __unwrap_iter(CheckedContiguousIterator iter) {
    return iter.current_;
  }
#endif

  constexpr CheckedContiguousIterator(T* start, const T* end) : CheckedContiguousIterator(start, start, end) {}
  constexpr CheckedContiguousIterator(const T* start, T* current, const T* end)
      : start_(start), current_(current), end_(end) {
    CHECK_LE(start, current);
    CHECK_LE(current, end);
  }
  constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) = default;

  // Converting constructor allowing conversions like CCI<T> to CCI<const T>,
  // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
  // are unsafe. Furthermore, this is the same condition as used by the
  // converting constructors of std::span<T> and std::unique_ptr<T[]>.
  // See https://wg21.link/n4042 for details.
  template <typename U, std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
  constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
      : start_(other.start_), current_(other.current_), end_(other.end_) {
    // We explicitly don't delegate to the 3-argument constructor here. Its
    // CHECKs would be redundant, since we expect |other| to maintain its own
    // invariant. However, DCHECKs never hurt anybody. Presumably.
    DCHECK_LE(other.start_, other.current_);
    DCHECK_LE(other.current_, other.end_);
  }

  ~CheckedContiguousIterator() = default;

  constexpr CheckedContiguousIterator& operator=(const CheckedContiguousIterator& other) = default;

  friend constexpr bool operator==(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ == rhs.current_;
  }

  friend constexpr bool operator!=(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ != rhs.current_;
  }

  friend constexpr bool operator<(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ < rhs.current_;
  }

  friend constexpr bool operator<=(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ <= rhs.current_;
  }
  friend constexpr bool operator>(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ > rhs.current_;
  }

  friend constexpr bool operator>=(const CheckedContiguousIterator& lhs, const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ >= rhs.current_;
  }

  constexpr CheckedContiguousIterator& operator++() {
    CHECK_NE(current_, end_);
    ++current_;
    return *this;
  }

  constexpr CheckedContiguousIterator operator++(int) {
    CheckedContiguousIterator old = *this;
    ++*this;
    return old;
  }

  constexpr CheckedContiguousIterator& operator--() {
    CHECK_NE(current_, start_);
    --current_;
    return *this;
  }

  constexpr CheckedContiguousIterator operator--(int) {
    CheckedContiguousIterator old = *this;
    --*this;
    return old;
  }

  constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
    if (rhs > 0) {
      CHECK_LE(rhs, end_ - current_);
    } else {
      CHECK_LE(-rhs, current_ - start_);
    }
    current_ += rhs;
    return *this;
  }

  constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
    CheckedContiguousIterator it = *this;
    it += rhs;
    return it;
  }

  constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
    if (rhs < 0) {
      CHECK_LE(-rhs, end_ - current_);
    } else {
      CHECK_LE(rhs, current_ - start_);
    }
    current_ -= rhs;
    return *this;
  }

  constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
    CheckedContiguousIterator it = *this;
    it -= rhs;
    return it;
  }

  constexpr friend difference_type operator-(const CheckedContiguousIterator& lhs,
                                             const CheckedContiguousIterator& rhs) {
    lhs.CheckComparable(rhs);
    return lhs.current_ - rhs.current_;
  }

  constexpr reference operator*() const {
    CHECK_NE(current_, end_);
    return *current_;
  }

  constexpr pointer operator->() const {
    CHECK_NE(current_, end_);
    return current_;
  }

  constexpr reference operator[](difference_type rhs) const {
    CHECK_GE(rhs, 0);
    CHECK_LT(rhs, end_ - current_);
    return current_[rhs];
  }

  static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin,
                              const CheckedContiguousIterator& from_end,
                              const CheckedContiguousIterator& to) WARN_UNUSED_RESULT {
    if (from_end < from_begin)
      return false;
    const auto from_begin_uintptr = get_uintptr(from_begin.current_);
    const auto from_end_uintptr = get_uintptr(from_end.current_);
    const auto to_begin_uintptr = get_uintptr(to.current_);
    const auto to_end_uintptr = get_uintptr((to + std::distance(from_begin, from_end)).current_);

    return to_begin_uintptr >= from_end_uintptr || to_end_uintptr <= from_begin_uintptr;
  }

 private:
  constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
    CHECK_EQ(start_, other.start_);
    CHECK_EQ(end_, other.end_);
  }

  const T* start_ = nullptr;
  T* current_ = nullptr;
  const T* end_ = nullptr;
};

template <typename T>
using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;

}  // namespace common
